package sort;

/**
 * 快速排序
 *
 */
public class QuickSort implements ISort{

	public void sort(int[] arr) {
		sortPartArr(arr, 0, arr.length - 1);
	}

	/**
	 * @param arr
	 * @param start 包含
	 * @param end   包含
	 */
	public void sortPartArr(int[] arr, int start, int end) {
		if (start >= end) {
			return;
		}
		int base = arr[start];						//为了方便，将第一个元素作为基准
		int leftPos = start;						//左游标指向第一个元素
		int rightPos = end;							//右游标指向最后一个元素
		A: while (true) {
			while (arr[rightPos] >= base) {			//每次都是从右游标开始移动，由于最后总需要将右游标指向数和基准数做交换，而右游标总是指向比基准小的数
				if (rightPos == leftPos) {			//左右游标相遇时结束循环
					break A;
				}
				rightPos--;
			}
			while (arr[leftPos] <= base) {
				if (rightPos == leftPos) {
					break A;
				}
				leftPos++;
			}
			int tmp = arr[rightPos];
			arr[rightPos] = arr[leftPos];
			arr[leftPos] = tmp;
		}
		arr[start] = arr[rightPos];
		arr[rightPos] = base;

		sortPartArr(arr, start, rightPos - 1);
		sortPartArr(arr, rightPos + 1, end);
	}

	public static void main(String[] args) {
		QuickSort quickSort = new QuickSort();
		int arr[] = { 8, 4, 7, 9, 6, 3, 1, 2, 5 };
		quickSort.sort(arr);
		ISort.printArr(arr);
	}
}
